import java.util.ArrayList;
/**
 * Created by L.jp
 * Description:给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，
 * 请找到 o1 和 o2 的最近公共祖先节点。
 * User: 86189
 * Date: 2022-06-27
 * Time: 11:34
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
  }
/**
 * @author 86189
 */
public class Solution {
    /* 法一：非递归 ，叫做路径比较法
            分别从左右子树两边使用dfs查找目标值，使用一个布尔值flag记录是否找到目标值的路径
            使用一个动态数组存储每一个遍历到的节点，也叫作存储路径，
            如果当前节点等于目标值，那么就返回,flag置为已经找到了
            如果一直遍历到叶子节点，也没有找到，那么就使用回溯法把数组最后一个节点删除
            从另一个子树那么开始找
    * */
    boolean hasPath=false;
    //存储根节点到目标值的路径
    public void getPath(TreeNode root,ArrayList<Integer> path,int o){
        if(root==null){
            return;
        }
        //把遍历到的每一个节点都加入数组，也就是存储路径
        path.add( root.val );
        if(root.val==o){
            //当前节点的值如果等于目标值，那么就说明找到了路径，可以返回
            hasPath=true;
            return;
        }
        //如果没有匹配目标值，那么就分别从左右子树开始找
        getPath( root.left,path,o );
        getPath( root.right,path,o );
        //如果有一边子树找到了路径，那么就回溯去删掉数组的最后一个节点，记录另一边的
        if(hasPath){
            return;
        }
        //如果没有找到就回溯把最后的节点删了
        path.remove( path.size()-1 );
    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        ArrayList<Integer> path1 = new ArrayList<Integer>();
        ArrayList<Integer> path2 = new ArrayList<Integer>();
        //遍历整个树找到o1的路径
        getPath(root,path1,o1);
        //重置标记，找另一个目标值的路径
        hasPath=false;
        //遍历整个树找到o2的路径
        getPath(root,path2,o2);
        int res=0;
        for(int i = 0; i <path1.size() && i<path2.size(); i++){
            int x=path1.get(i);
            int y=path2.get(i);
            //找到最后一次相同的节点值就是最近公共祖先
            //怎么找最后一次相同的节点，就是如果两个路径的元素值相同，那么就赋值给结果4
            //直到第一次出现不一样的值的时候就退出，那么上一次出现的相同值就是最近公共祖先
            if(x==y){
                res=x;
            }else{
                break;
            }
        }
        return res;
    }
}
